(1) Field of Invention
The present invention relates to data transmission and computer security systems and more particularly, to multi-cypher encryption and decryption, multi-source random number generation and to systems for transmitting multiple encrypted data streams.
In particular, the present invention relates to a random number generation and encryption method or system which uses a distributed framework of multiple random or pseudo-random number generators producing infinite length multiple keystreams, to support a dynamic super-encryption cipher-stream (a continuous sequence of variable length ciphertext segments each encrypted with a unique key) which is used to transmit data between system nodes, and also transmit random entropy updates which are used to perpetually augment the entropy or uncertainty of the cryptosystem mechanics, variables, configuration, state or the composition of the random number generators used to generate the required random number outputs.
(2) Description of the Related Art
Cryptography provides a means of security for transmitted data by transforming messages from “plaintext” to “ciphertext” using a secret “key” and an encryption and decryption algorithm.
This invention relates specifically to “true” secrecy cryptosystems, in that the meaning of the messages being transmitted are concealed by a cipher or code and the adversary is assumed to have any special equipment necessary to intercept and record the transmitted signal; as defined in the document—Shannon, Claude (1949) “Communication Theory of Secrecy Systems”, Bell System Tech. J., Vol. 28, pp. 656-715.
In typical “symmetric” encryption usage scenarios, the transmitted data is encrypted by a sender using a unique key value (such as a 256-bit binary number) and unscrambled at the receiver, by a reverse process that requires the same key value to be known, whereas with “asymmetric encryption”, different key values are used which are mathematical inverse functions of the first unique key value, such as ¼ and 4/1. Since these keys are almost always shorter than the messages they encrypt, a means of applying the key to longer messages is used. With block cyphers, the key is in essence repeated with every block of message data that is encrypted (may include a transformation of the key between blocks), whereas with stream ciphers the key is applied to a pseudo-random number generator (hereinafter called “PRNG”) to produce a long keystream which is then used for encryption and decryption purposes.
Ordinarily, the strength of a cryptosystem may be considered to be directly proportional to the length of the initial key, but this assumption is subject to the condition that the ciphertext is shorter than a value that Claude Shannon called the “unicity distance”. Cryptographic algorithms which produce ciphertexts which exceed the unicity distance, which is the length of the initial key plus the minimum length which could be used to convey the message, are inherently insecure, and are guaranteed to produce a single correct decipherment. Since the encryption strength of any encryption algorithm decays in proportion to the length of the ciphertext which exceeds the “unicity distance”, statistical decryption techniques such as equivocation are far more efficient than brute force decryption.
A simple and secure cryptosystem which is not subject to equivocation attack risks, has been around since 1882. The “one-time” pad (hereinafter referred to as “OTP”) or Vernam Cipher, was originally invented by Frank Miller and patented in 1917 by Gibert Vernam (U.S. Pat. No. 1,310,719 entitled “Secret Signalling System”). The OTP has the distinction as being the only cryptosystem to date to have been mathematically proven to be “perfectly secret” (as defined by Claude Shannon) if used correctly, in that an adversary is unable to compromise the cipher given infinite time, infinite computing resources, and any number of plaintext/cyphertext pairs. It is the object of this invention to introduce a new “information theoretically secure” cryptosystem.
The OTP's “perfect secrecy” is dependent on the following conditions being met: (1) The key used must be truly random—the key must therefore be unpredictable or insignificant in every sense of value, position or distribution, (2) The key must be at least as long as the plaintext, if not longer, and never repeated in whole or in part, and (3) The keys must be kept completely secret during generation, distribution, usage and storage.
Claude Shannon, in dealing with secrecy cryptosystems in general, asserted that the OTP complied with the requirements for “perfect secrecy”—namely that the ciphertext can be translated into any plaintext of the same length, all of which are equally likely, if a truly random key was used. More specifically, he defined “perfect secrecy” as meeting the criterion that “the a priori probability of a plaintext message M is the same as the a posteriori probability of a plaintext message M given the corresponding ciphertext”. Further, he explained that perfect secrecy is possible but requires that the keys must be generated at the same or higher rate than the messages, and be at least as long as the messages. Strictly speaking, by the above definition, perfect secrecy can never be obtained using block cyphers or seed-fed stream ciphers, since the input entropy is limited to the seed or key size.
Despite these cryptographic strengths, practical problems have prevented OTPs from being widely applied in a practical manner, including: (1) The Random Number Generation Problem—The problem in generating unpredictable infinite length one-time pad sequences, which is a serious problem if one is using single independent pseudo-random number generators (hereinafter called “PRNGs”), (2) The Distribution Problem—in that the required OTP values must be securely generated and exchanged between the sender and receiver, and be at least as long as the messages to be sent, and (3) The Key Management Problem—in that the OTPs must be kept secret and be immediately and irrevocably disposed of in a secure manner.
In addition to the problems mentioned above, the OTP also suffers from the following issues: (1) known ciphertext length, (2) ciphertext readily visible for analysis, (3) lack of user authentication, (4) lack of message verification and error correction, (5) ciphertext position is relative to plaintext.
In addressing the Random Number Generation problem with regards to “perfect secrecy” systems and the “one-time pad”, any numbers that are generated and used as keys in a cryptosystem must be truly random and thus, unpredictable in any conceivable manner. There are two principal methods or types of random number generators (hereinafter called RNGs) used currently to generate random numbers, namely “true random number generators” (hereinafter referred to as TRNGs) and “pseudorandom number generators” (hereinafter referred to as PRNGs). TRNGs measure some physical phenomenon that is expected to have random characteristics and compensate for possible biases in the measurement process. Drawbacks to this approach include the need for measuring apparatus, and there are limitations to the rate at which random numbers (or “entropy”—a measure of unpredictability of information content) can be harvested since there is a dependency on the underlying rate of measurement. PRNGs entail the use of computational algorithms or functions to produce long sequences of apparently random results, which are actually completely predetermined by a smaller initial value, or seed. PRNGs tend to be fast, and act alone with the exception of input seeds which can be provided independently or are functions of their output. There are two distinct types of PRNGs—linear congruential generators which use a mathematical calculation and use outputs as a means of deriving inputs in a cyclic manner, and probability distribution generators which perform various operations on a data set or table (such as ARC4—a well-known stream cypher). Since both types of PRNGs use small seed or initialization values, there is a cryptographic quality issue in that that the entropy of the output number sequences with a PRNG is limited to the entropy of the input seed entropy. For example, if a numeral from 1 to 9 is used as a seed in a pseudorandom number generator, there may be a maximum of 10 variations of output, irrespective of the length of their output sequences. Therefore, PRNGs initialized using a seed value cannot satisfy the requirements of “information theoretic” security since their output keys are only truly random until they exceed the length of the input seed key.
It is therefore a specific objective of the current invention to address the random number generation problem through the manipulation of multiple RNGs or more specifically, the manipulation of the RNG internal states, operating within the cryptographic system.
Since constant reuse or use (in the case of stream ciphers) of the same key is cryptographically insecure due to the consumption of key entropy through normal use (resulting in a reduction in equivocation), in order to increase security, encryption key values may be frequently changed (with a penalty to bandwidth usage) to continuously add entropy to the cryptosystem, reduce the probability that an adversary may compromise the cryptosystem by intercepting and deciphering the encrypted messages, and thus requires new key values to be sent frequently by the sender to the receiver. In U.S. Pat. No. 5,412,730, Michael F. Jones “Encrypted Data Transmission System Employing Means for Randomly Altering the Encryption Key” we find such a method whereby new keys may be generated by a single independent RNG located at the sender, encrypted with the currently active key and transmitted along with normal data. Following decryption of the cipher-stream at the receiving station or entity, the encrypted keys are extracted from the data-stream, decrypted, and substituted for the prior key at a predetermined or designated point in time.
However, even such dynamic systems have numerous weaknesses, in that (a) pseudorandom keys are generated using PRNGs which eventually become predictable, (b) keys are stored and susceptible to interception and compromise, (c) keys are limited in length, and thus present a limit in cryptographic entropy and strength, even though resultant pseudo-key material is longer than the original key, (d) keys are reused, or transformed in a linear manner through functions, making equivocation analysis attacks viable, (e) the ciphertext is readily visible facilitating cryptanalysis attack and (f) the above issues lead to situations where the deciphering of a single key leads to compromise of successive and previous keys, and eventually to a compromise of all previous and future transmitted data.
In accordance with a principle feature of the present invention, multiple RNGs are deployed at both the sending and receiving stations or entities (may be users, machines, network devices, groups etc.) in that some RNGs are used to generate a sequence of random entropy values, which are mixed with message sequences, and communicated in an encrypted format, and are then used to alter the deterministic mechanics of the cryptosystem or it's RNGs in a probabilistic manner without actually communicating any keys, but merely the means of key generation. This mechanism therefore serves to “update” the entropy of the cryptosystem which ordinarily would be limited to the initial keys used, and will allow for an information theoretically secure cryptosystem, provided the rate of entropy updates exceeds the rate of entropy depletion. Whilst it is possible to pass new keys along in such a manner, or to pass updates which can be applied to existing keys to generate new keys, the rate of entropy depletion will usually be greater than the rate of entropy updates, which is why this technique is not generally used in cryptography. The solution to the problem of updating entropy at a faster rate than the depletion can be accomplished if a large entropy pool is used such as that found in a stateful random number generator. Merely passing the entropy updates between sender and receiver does not divulge any resultant keystreams or keys. In addition, provided an independent RNG is used to generate the entropy updates, and the entropy values are pre-encrypted with a shared key before being joined to normal messages or control values in randomly composed encryption blocks, and subsequently encrypted with the outputs of a second RNG, it is mathematically possible to augment the rate of entropy (or uncertainty) in the cryptosystem faster than it can be depleted through normal use. Doing this in a perpetually synchronized manner between sender and receiver, effectively results in a perpetual information theoretically secure cryptosystem, provided the proportion of entropy updates is larger than the amount of redundancy in the messages being communicated.
In accordance with the invention, in order to allow the two sending and receiving entities to continue communication using a random keystream, each is supplied in advance with a separate random number sequence which exclusively determines the numerical sequence and content of the random numbers produced by the two synchronized RNGs. Whilst the separate random number sequence may be used as a seed to restart the random number generation process at a predetermined time (as is found in prior art), it can alternatively be used to great advantage to alter a portion or the entirety of the output sequences of the RNGs, by altering a portion or the entirety of their internal states. Alternatively, it can be used for other purposes, such as allowing for variation in the encryption mechanics used, or for altering a portion or the entirety of the encrypted ciphertext prior to transmission.
In accordance with the principle feature of the invention, an additional independent entropy source like another RNG is used to generate random sequences of numbers of random length (entropy), which is then randomly and continuously injected into the data-stream or crypto-stream of stream ciphers, or into block ciphers, in order to randomly alter various components of the cryptosystem separately or in union, namely the output, the mechanics or the internal states of random number generators, or the mechanics or composition of the encryption algorithms, or the composition or characteristics of the plaintext prior to encryption, or the ciphertext after encryption prior to transmission. In order that the two generators switch from the previous cryptographic configuration to the next in synchronicity, means are employed at the sender to construct transmission packages which include data messages, random update information, other information and control information. Following encryption at the sender, transmission and decryption at the receiver, previous control information is used to deconstruct the package into its separate components and process data, updates, other information and control information accordingly. The construction and encryption, or deconstruction and decryption, of transmission packages (which may be fixed or randomly variable in length), may be referred to as an “encryption cycle”. Following the completion of an encryption cycle at the sender or the receiver, encryption configuration changes are applied to the respective cryptosystem components, and the new control information variables become active, replacing the old control variables. This continuous update process continues indefinitely until the communication link is terminated.
Without reiterating the above problems, it is therefore an object of the current invention to provide a method and a system which addresses the above problems whilst remaining within the confines of the characteristics of a “perfect secrecy” cryptosystem.
Until 1976, symmetric cryptosystems (that use a similar encryption and decryption key) like the one-time pad, were the predominant cryptosystem in practice. Unlike the one-time pad, most symmetric cryptosystems were block cyphers or stream ciphers, which used keys that were usually smaller than the message being transmitted. In the case of block ciphers the use of smaller repeating keys is not a cryptographically secure means of encryption, for two reasons, firstly it results in a decrease in the size of the cryptographic problem (by limiting the amount of cryptographic input entropy in a cryptosystem—the reason why “one time” pads should have keys as long as the message), and secondly, it allows for the implementation of equivocation techniques which use statistical means to compromise the cipher without having to resort to brute force techniques of trying every possible key (the reason why keys should never be repeated). Stream ciphers on the other hand use small keys as seeds to PRNGs for the generation of lengthy output keystreams, but the use of limited length seeds again results in a decrease of cryptographic entropy of the output key stream, the very reason why “perfect secrecy” systems require keys to be as long as the message. For stream ciphers or block ciphers to attain “perfect secrecy”, they must continuously receive random seeds, which results in 100% overhead to their message length and decreases their processing efficiency.
It is therefore a specific objective of the current invention to address the problem with ensuring that the one-time perpetual keys that are generated within the cryptosystem, can be initiated by a single set of initialisation values or keys, yet be able to maintain their unpredictable and perpetually random nature, through random feedback and synchronization updates between RNGs operating within the cryptographic system.
Like the one-time pad, all symmetric ciphers had the inherent “Distribution Problem” in that the original keys or seeds used for encryption and decryption must first be communicated between sender and receiver using a secure means of transfer. The security of any cryptographic system is only as secure as the initial key exchange, and the transfer process is prone to theft, interception, and alteration, defeating the purpose of the underlying cryptosystem.
The invention of asymmetric encryption (using different but related keys to encrypt and decrypt—such as private and public keys) addressed the distribution problem to a large extent allowing for limited length key distribution over insecure communication links, whilst also introducing authentication, verification and revocation properties which were previously absent in symmetric cryptosystems, an enormous achievement. However, this was achieved at the considerable expense of replacing previously mathematically proven “secure” (unbreakable) cryptosystems with a design alternative that relied on the unproven or assumed difficulty of solving certain mathematically “hard” problems.
It is therefore apparent that a need exists for a cryptosystem or cryptographic technique to address the issues that hampered the practical adoption of the one-time pad, by solving the randomness problem, the distribution problem, the key management problem, allowing for the use of asymmetric encryption advantages through the use of efficient super-encryption without compromising sound cryptographic principles by adhering to the basic requirements of a “perfect secrecy” cryptosystem. The present invention is directed toward providing such a technique and is unique in combining an autonomous network of multiple independent RNGs and an efficient super-encryption capability which is able to support asymmetric encryption solutions, as a viable means of addressing the problems mentioned above.
It is an object of the current invention to use the basic mechanics and principles of the OTP (true random numbers as long as the messages) as a foundation to the cryptosystem, and augmenting it where necessary with techniques to address past issues and keep all cryptosystem mechanics and functions dynamic, autonomous and independent from direct user interaction due to key input or message content. Thus ensuring that keys or RNG states are not readily available to user access since individual key values are automatically and dynamically generated, used and destroyed.
It is therefore an object of the current invention to provide a method and a system for the proper and cryptographically secure generation of unpredictable random numbers by dynamically and randomly synchronizing the state of independent random and pseudo-random number generators (RNGs) in an interconnected RNG communication network. The propagation of synchronicity entropy changes at a specific system node has the desirable side-effect in that its entropy impact may eventually be propagated across the entire network to other connected system nodes.
Another object of the current invention is to use the cryptographically secure output of multiple RNGs to perpetually and randomly add entropy to the encryption sequence in a manner similar to that found in prior art and referred to as “dynamic encryption” systems. Dynamic encryption attempts are described in U.S. Pat. No. 7,376,232, by Hamdy Soliman entitled “Computer System Security Via Dynamic Encryption”, and U.S. Pat. No. 5,412,730 by Michael F. Jones entitled “Encrypted Data Transmission System Employing Means for Randomly Altering the Encryption Keys”, but the present invention differs from previous art substantially in that it does not rely on the limited entropy of previous keys or data as a means of dynamic propagation, nor do keys get transferred over communication link, but in the transfer of an random length RNG state changes within a super-encrypted cipher-stream, which presents a more efficient and stochastic improvement, albeit at the price of expansion in message length, another reason why this technique does not appear in prior art, since message expansion is generally considered undesirable.
With regard to stream cyphers, ARC4, designed by Ron Rivest in 1987 and leaked to the public in 1994, is remarkable in its simplicity and speed in software. However, ARC4 has vulnerable weaknesses that argue against its use in new systems, such as not discarding the beginning of output streams, or when nonrandom keys are used. Additional problems identified by cryptanalysts with ARC4 include (a) a weak initial key scheduling algorithm, (b) a predictable starting distribution, (c) a uniform value distribution in that each value in the 256 byte secret state is unique and changed in location only, (d) a lack of additional input entropy following initialisation.
It is an object of this invention to introduce a viable and dynamic RNG (identified in the invention as a “Hi-Generator”) which addresses the problems identified with ARC4. Besides differences in the secret internal index pointers and state size, which can be randomly predetermined to be less or higher than 256 bytes, and can dynamically change its size during operation, it has no scheduling algorithm, nor a uniform distribution of unique values—all state values are random. In addition the pseudo-random generation algorithm does not merely relocate values, but amends them, in that each operation results in 3 or more additionally amended values. The most important difference being introduced with Hi-Generators, is that independent dynamic random changes are intermittently performed on the internal secret state of the RNG during normal operations, through the use of entropy updates. To conserve entropy, amended values need not be discarded but can be transferred to other Hi-Generators. These updates may be applied in an effort to synchronize variations in the output stream between synchronized RNGs, or to distribute the impact of entropy updates to unsynchronized RNGs.
A further object of the current invention is to simultaneously super-encrypt the combined data transmissions and entropy updates within a variable length message package, thereby using the RNG synchronization updates to “pollute” or “contaminate” the resulting cipher-text sequence for the message, making the cryptosystem resistant to linear and differential cryptanalysis, and removing the assumption that a message was even sent.
A further object of the current invention is to provide an efficient technique for the super-encryption of messages that incurs less than 100% overhead in message length, and which is able to shield the cipher-text from cryptographic analysis and address the “magic number” and “null string” problems.
A further object of the current encryption is to allow for the integration of existing authentication and verification asymmetric encryption mechanisms (used for user authentication, identification information, keys or certificates) into the encryption process itself, greatly adding to the security of asymmetric encryption systems and extending the present invention cryptosystem to include central authority control and management functions, and supporting the distribution and authentication of cryptosystem entities (users, machines, systems, data, access control and services etc.), the establishment of secure communication links between vetted entities, and eliminate the possibility of unidentified entities communicating to any other entity within in the cryptosystem network.
A further object of the invention is to provide a single efficient, fast and scalable means of encryption which can be used for all eventualities, namely encryption of data at rest, data in transit over communication channels, and for the provision of a means of authenticating network entities.
A further object of the invention is to provide a means for ensuring that all traffic flowing within the cryptosystem network remains behind a logical security boundary, whereby access to and from specific system nodes is controlled identified and kept under user or management control.
These and other objects, features and advantages of the invention will be apparent to those skilled in the art, and more clearly understood by considering the following detailed description of specific embodiments of the invention.